import numpy as np
from collections import Counter

class KNeighborsClassifier:
    def __init__(self, n_neighbors=5, weights='uniform', metric='euclidean'):
        """
        初始化 KNN 分类器的超参数
        参数:
        n_neighbors (int): 用于分类的邻居数，默认为 5
        weights (str): 权重函数，默认为 'uniform'
        metric (str): 距离度量方式，默认为 'euclidean'
        """
        self.n_neighbors = n_neighbors
        self.weights = weights
        self.metric = metric

    def fit(self, X, y):
        """
        训练 KNN 分类器
        参数:
        X (ndarray): 训练数据集，形状为 (n_samples, n_features)
        y (ndarray): 训练标签，形状为 (n_samples,)
        """
        self.X_train = X  # 保存训练数据
        self.y_train = y  # 保存训练标签

    def predict(self, X):
        """
        对新数据进行预测
        参数:
        X (ndarray): 输入数据集，形状为 (n_samples, n_features)

        返回:
        ndarray: 预测标签，形状为 (n_samples,)
        """
        predictions = [self._predict(x) for x in X]
        return np.array(predictions)

    def _predict(self, x):
        """
        预测单个样本的标签
        参数:
        x (ndarray): 输入样本，形状为 (n_features,)

        返回:
        int: 预测的标签
        """
        # 计算每个训练样本到当前样本的距离
        if self.metric == 'euclidean':
            distances = np.linalg.norm(self.X_train - x, axis=1)
        elif self.metric == 'manhattan':
            distances = np.sum(np.abs(self.X_train - x), axis=1)
        else:
            raise ValueError("Unsupported metric")

        # 获取最近的 k 个样本的索引
        k_indices = np.argsort(distances)[:self.n_neighbors]

        # 获取这些样本的标签
        k_nearest_labels = self.y_train[k_indices]

        # 进行多数投票或权重投票
        if self.weights == 'uniform':
            most_common = Counter(k_nearest_labels).most_common(1)
            return most_common[0][0]
        elif self.weights == 'distance':
            weights = 1 / distances[k_indices]
            weighted_votes = np.zeros_like(k_nearest_labels, dtype=float)
            for i, label in enumerate(k_nearest_labels):
                weighted_votes[i] = weights[i]
            weighted_counts = Counter({label: 0 for label in np.unique(k_nearest_labels)})
            for i, label in enumerate(k_nearest_labels):
                weighted_counts[label] += weighted_votes[i]

            return max(weighted_counts, key=weighted_counts.get)
        else:
            raise ValueError("Unsupported weights")

    def score(self, X, y):
        """
        计算模型的准确度
        参数:
        X (ndarray): 测试数据集，形状为 (n_samples, n_features)
        y (ndarray): 测试标签，形状为 (n_samples,)

        返回:
        float: 准确率
        """
        y_pred = self.predict(X)
        return np.mean(y_pred == y)